package main

type Trie struct {
	Root *Node
}

type Node struct {
	Children map[byte]*Node
	isEnd    bool
}

/** Initialize your data structure here. */
func Constructor() Trie {
	return Trie{Root: &Node{
		Children: make(map[byte]*Node),
	}}
}

/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
	node := this.Root
	for _, c := range word {
		next, ok := node.Children[byte(c)]
		if ok {
			node = next
		} else {
			// start insert
			next = &Node{
				Children: make(map[byte]*Node),
			}
			node.Children[byte(c)] = next
			node = next
		}
	}
	node.isEnd = true
}

/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
	node := this.Root
	for _, c := range word {
		next, ok := node.Children[byte(c)]
		if ok {
			node = next
		} else {
			return false
		}
	}
	return node != nil && node.isEnd
}

/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
	node := this.Root
	for _, c := range prefix {
		next, ok := node.Children[byte(c)]
		if ok {
			node = next
		} else {
			return false
		}
	}
	return true
}

/**
 * Your Trie object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Insert(word);
 * param_2 := obj.Search(word);
 * param_3 := obj.StartsWith(prefix);
 */

func main() {
	trie := Constructor()
	trie.Insert("abc")
	println(trie.StartsWith("acd"))
}
